package leetcode;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class lc219 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,1,2,3};
        containsNearbyDuplicate(nums,2);
    }
    /**
     * Input: nums = [1,2,3,1], k = 3
     * Output: true
     */
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, List<Integer>> hashMap = new HashMap<>();
        for(int i=0;i<nums.length;++i){
            if(hashMap.containsKey(nums[i])){
                Integer key = nums[i];
                List<Integer> valueList = hashMap.get(nums[i]);
                valueList.add(i);
                hashMap.replace(key,valueList);
            }else{
                List<Integer> valList = new ArrayList<>();
                valList.add(i);
                hashMap.put(nums[i],valList);
            }
        }

        for(Map.Entry<Integer,List<Integer>> pair:hashMap.entrySet()){
            List<Integer> valList = pair.getValue();
            for(int i=0;i<valList.size();++i){
                for(int j=i+1;j<valList.size();++j){
                    if(j-i <= k) return true;
                }
            }
        }
        return false;
    }
}
